package com.lijing.avlTree;

/**
 * @Description 平衡二叉树
 * @title: AvlTree
 * @Author LiJing
 * @Date: 2021/3/2910:58 下午
 * @Version 1.0
 */
public class AvlTree {
    private Node root;

    /**
     * add a Node
     * @param node the node to be added
     */
    public void add(Node node){
        if (root == null){
            root = node;
        }else {
            root.add(node);
        }
    }

    public Node search(int value){
        if (root == null){
            return null;
        }
        return root.search(value);
    }
    public Node searchParent(int value){
        if (root == null){
            return null;
        }
        return root.searchParent(value);
    }

    /**
     * 删除节点
     * @param value 待删除的节点值
     */
    public void delNode(int value){
        if (root == null){
            return;
        }
        else {
            Node targetNode = search(value);
            if (targetNode == null){
                return;
            }
            /**
             * 删除根节点
             */
            if (null == root.getLeft() && null == root.getRight()){
                root = null;
            }
            Node parent = searchParent(value);
            /*
             * @Date: 2021/3/30 12:00 上午
             * Step 1: 删除的是叶子节点
             */
            if (targetNode.isLeafNode()){
                if (parent.getLeft() != null && parent.getLeft().getValue() == value){
                    parent.setLeft(null);
                }else if (parent.getRight() != null && parent.getRight().getValue() == value){
                    parent.setRight(null);
                }
            }
            /*
             * @Date: 2021/3/30 12:07 上午
             * Step 2: 有两个子树
             */
            else if (targetNode.getLeft() != null && targetNode.getRight() != null){
                Node temp = targetNode.getLeft().getMaxNode();
                delNode(temp.getValue());
                targetNode.setValue(temp.getValue());
            }
            /*
             * @Date: 2021/3/30 12:07 上午
             * Step 3: 有一个子树
             */
            else {
                //有左子节点
                if (targetNode.getLeft() != null){
                    if (parent.getLeft() != null && parent.getLeft().getValue() == targetNode.getValue()){
                        parent.setLeft(targetNode.getLeft());
                    }else {
                        parent.setRight(targetNode.getLeft());
                    }
                }
                //有右子节点
                else if (targetNode.getRight() != null){
                    if (parent.getLeft() != null && parent.getLeft().getValue() == targetNode.getValue()){
                        parent.setLeft(targetNode.getRight());
                    }else {
                        parent.setRight(targetNode.getRight());
                    }
                }
            }


        }
    }

    public void leftChange(){

    }


    /**
     * infixOrder
     */
    public void infixOrder(){
        if (root == null){
            System.out.println("the AvlTree is empty!");
        }else {
            root.infixOrder();
        }
    }
    public AvlTree(Node root) {
        this.root = root;
    }

    public AvlTree() {
    }
    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
}
